package LinkedList;

import Node.ListNode;

public class ReverseKGroup {

    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null)
            return null;
        // 区间[a,b)包含k个待反转元素
        ListNode a, b;
        a = b = head;
        for (int i = 0; i < k; i++) {
            // 不足k个，不需要反转
            if (b == null)
                return null;
            b = b.next;
        }
        // 反转前k个元素
        ListNode newHead = reverseN(a, k);
        // 此时，b 指向下一组待反转的头结点
        // 递归反转后续的链表并连接起来
        a.next = reverseKGroup(b, k);
        return newHead;
    }

    private ListNode reverseN(ListNode head, int k) {
        if (head == null || head.next == null)
            return head;
        ListNode prev, cur, next;
        prev = null;
        cur = head;
        next = head.next;
        while (k > 0) {
            cur.next = prev;
            prev = cur;
            cur = next;
            if (next != null)
                next = next.next;
            k--;
        }
        head.next = cur;
        return prev;
    }
}
